package com.cqs.leetcode.recursion;

import com.cqs.leetcode.TreeNode;

/**
 * @author lixiaowen
 * @create 2019-12-10
 */
public class ValidateBinarySearchTree98 {

    public boolean isValidBST(TreeNode root) {
        return isValidSubTree(root,null, null);
    }


    /**
     *
     * @param root 当前树根节点
     * @param min  最小值，用于和右子树校验
     * @param max  最大值， 用于和左子树教研
     * @return
     */
    public boolean isValidSubTree(TreeNode root, Integer min, Integer max){
        //递归结束条件
        if(root == null) return true;
        //检验右子树的时候,min为空。检验左子树的时候min不为null
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;

        //root.val是root.left子树的max值。 root.val是root.right子树的最小值
        return isValidSubTree(root.left,min, root.val )
                && isValidSubTree(root.right,root.val, max);
    }
}
